/**
 * 416.分割等和子集
 */
public class Exerciser2 {
    public boolean canPartition(int[] nums) {
        // 使用滚动数组优化，单数组

        // 把题转换成：在数组中选一些值，看这些值是否可以等于 数组和/2
        int sum = 0;
        int n = nums.length;
        for(int i = 0;i < n;i++) {
            sum += nums[i];
        }
        if(sum % 2 == 1) {
            // 为奇数，整除不开
            return false;
        }

        int mid = sum / 2;
        // dp[i][j]: 从前i个数中选取值，所有选法中，能否凑成 j 这个数
        boolean[] dp = new boolean[mid + 1];
        // 初始话，当i为0时，j为1-mid这些位置的值均为false,当j为0时候i位置均为true
        dp[0] = true;
        for(int i = 1; i <= n;i++) {
            for(int j = mid;j >= nums[i - 1];j--) {
                dp[j] = dp[j] || dp[j - nums[i - 1]];
            }
        }

        return dp[mid];
    }

    public boolean canPartition1(int[] nums) {
        // 把题转换成：在数组中选一些值，看这些值是否可以等于 数组和/2
        int sum = 0;
        int n = nums.length;
        for(int i = 0;i < n;i++) {
            sum += nums[i];
        }
        if(sum % 2 == 1) {
            // 为奇数，整除不开
            return false;
        }

        int mid = sum / 2;
        // dp[i][j]: 从前i个数中选取值，所有选法中，能否凑成 j 这个数
        boolean[][] dp = new boolean[n + 1][mid + 1];
        // 初始话，当i为0时，j为1-mid这些位置的值均为false,当j为0时候i位置均为true
        for(int i = 0;i <= n;i++) {
            dp[i][0] = true;
        }

        for(int i = 1; i <= n;i++) {
            for(int j = 1;j <= mid;j++) {
                // 不选择最后一个位置的值，肯定存在，不添加前置条件
                dp[i][j] = dp[i - 1][j];
                if(j >= nums[i - 1]) {
                    // 选择最后一个位置，需要添加一个前置条件
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }

        return dp[n][mid];
    }
}
